#pragma once

#include "big_int.h"
#include "vector.h"

#include <iostream>
#include <cmath>
#include <string>
#include <cstdlib>

big_int::big_int(int64 t): num(Vector(1))
{
   num[0] = abs(t);
   negative = (t < 0);
   
}

big_int::big_int(const big_int& num_):
   num(num_.num),
   negative(num_.negative)
{
}

big_int::big_int(const Vector& num_, bool negative_)
{
   negative = negative_;
   num = num_;
}

big_int& big_int::operator=(const big_int& num_) {
   negative = num_.negative;
   num = num_.num;
   return *this;
}

big_int::big_int(const std::string s)
{
   std::string s1 = s;
   bool negative_ = false;
   if (s1[0] == '-')
   {
      negative_ = true;
      s1 = s1.substr(1, s1.size() - 1);
   }
   int size_ = s1.size();
   int length_ = (size_ - 1) / big_int::base_length + 1;
   num = Vector(length_);
   for (int i = size_ - 1, j = 0; i >= 0; i -= big_int::base_length, j++)
      if (i >= big_int::base_length)
         num[j] = atol(s1.substr(i - big_int::base_length + 1, big_int::base_length).c_str());
      else
         num[j] = atol(s1.substr(0, i + 1).c_str());
   *this = big_int(num, negative_);
}

void big_int::swap(big_int &num_)
{
   num.swap(num_.num);
   std::swap(negative, num_.negative);
}

void swap(big_int& num1, big_int& num2)
{
   std::swap(num1, num2);
}

bool big_int::operator==(const big_int& num_) const
{
   if (negative != num_.negative)
      return false;
   for (size_t i = 0; i < std::max(num.size(), num_.num.size()); i++)
      if (num[i] != num_.num[i])
         return false;
   return true;
}

bool big_int::operator<(const big_int& num_) const
{
   if (negative != num_.negative)
      return negative;
   if (negative)
      return abs(num_) < abs(*this);
   for (int i = std::max(num.size(), num_.num.size()) - 1; i >= 0; i--)
      if (num[i] != num_.num[i])
         return num[i] < num_.num[i];
   return false;
}

bool operator>(const big_int& num1, const big_int& num2)
{
   return num2 < num1;
}

bool operator<=(const big_int& num1, const big_int& num2)
{
   return !(num1 > num2);
}

bool operator>=(const big_int& num1, const big_int& num2)
{
   return !(num2 > num1);
}

bool operator!=(const big_int& num1, const big_int& num2)
{
   return !(num1 == num2);
}

big_int operator-(big_int num_)
{
   num_.negative = !num_.negative;
   return num_;
}

big_int& big_int::operator+=(const big_int& num_)
{
   int s = (!negative * 2 - 1);
   for (size_t i = 0; i < std::max(num.size(), num_.num.size()); i++)
   {
      num[i] = num[i] * s + num_.num[i] * (!num_.negative * 2 - 1);
      if (num[i] >= big_int::base)
      {
         num[i] -= big_int::base;
         num[i + 1] += s;
      }
      if (num[i] <= - big_int::base)
      {
         num[i] += big_int::base;
         num[i + 1] -= s;
      }
   }
   int new_size = num.size() - 1;
   while ((new_size > 0) && (num[new_size] == 0))
      new_size--;
   negative = (num[new_size] < 0);
   if (num[new_size] < 0)
      num[new_size] = -num[new_size];
   for (int i = new_size - 1; i >= 0; i--)
   {
      if ((!negative) && (num[i] < 0))
      {
         num[i] += base;
         num[i + 1]--;
      }
      if ((negative) && (num[i] > 0))
      {
         num[i] -= big_int::base;
         num[i + 1]--;
      }
      if (num[i] < 0)
         num[i] = -num[i];
   }
   return *this;
}

big_int& big_int::operator-=(const big_int& num_)
{
   return *this += (-num_);
}

big_int operator+(big_int num1,const big_int& num2)
{
   return num1 += num2;
}

big_int operator-(big_int num1,const big_int& num2)
{
   return num1 -= num2;
}

big_int& big_int::operator*=(int64 int_)
{
   if ((int_ < 0) && (*this != 0))
      negative = !negative;
   for (size_t i = 0; i < num.size(); i++)
      num[i] *= abs(int_);
   for (size_t i = 0; i < num.size(); i++)
   {
      if (num[i] >= big_int::base)
         num[i + 1] += num[i] / big_int::base;
      num[i] %= big_int::base;
   }
   return *this;
}

big_int operator*(big_int num_, int64 int_)
{
   return num_ *= int_;
}

big_int& big_int::operator*=(const big_int& num_)
{
   big_int tmp1 = 0;
   big_int tmp2 = *this;
   for (size_t i = 0; i < num_.num.size(); i++)
   {
      tmp1 += tmp2 * num_.num[i];
      tmp2 *= big_int::base;
   }
   if (tmp1 != 0)
      tmp1.negative = (negative ^ num_.negative);
   *this = tmp1;
   return *this;
}

big_int operator*(big_int num1, const big_int& num2)
{
   return num1 *= num2;
}

big_int& big_int::operator/=(const big_int& num_)
{
   big_int divident = *this;
   divident.negative = false;
   big_int ans = 0;
   big_int tmp = num_;
   tmp.negative = false;
   int t = 0;
   while (tmp < divident)
   {
      tmp *= base;
      t++;
   }
   while (t >= 0)
   {
      int64 l = -1;
      int64 r = big_int::base + 1;
      while (l + 1 < r)
      {
         int64 c = (l + r) / 2;
         if (divident  >= tmp * c)
            l = c;
         else
            r = c;
      }
      ans *= big_int::base; 
      ans += big_int(l);
      divident -= tmp * l;
      for (size_t i = 0; i < tmp.num.size() - 1; i++)
      tmp.num[i] = tmp.num[i + 1];
      tmp.num[tmp.num.size() - 1] = 0;
      t--;
   }
   if (ans != 0)
      ans.negative = (negative ^ num_.negative);
   *this = ans;
   return *this;
}

big_int operator/(big_int num1, const big_int& num2)
{
   return num1 /= num2;
}

big_int abs(big_int num_)
{
   num_.negative = false;
   return num_;
}

big_int& big_int::operator%=(const big_int& num_)
{
   *this -= (num_ * (*this / num_));
   return *this;
}

big_int operator%(big_int num1, const big_int &num2)
{
   return num1 %= num2;
}

std::ostream& operator<<(std::ostream& os, const big_int& num_)
{
   int n = num_.num.size();
   while (num_.num[n - 1] == 0 && n > 1) 
      n--;
   if (n == 1 && num_.num[0] == 0)
   {
      os << "0";
      return os;
   }
   if (num_.negative)
      os << "-";
   os << num_.num[n - 1];
   for (int i = n - 2; i >= 0; i--)
   {
      int64 now = num_.num[i];
      int64 now2 = now;
      int len = 0;
      for (len = 0; now2 > 9; now2 /= 10, len++);
      for (int i = 0; i < big_int::base_length - len - 1; i++)
         os << "0";
      os << now;
   }
   return os;
}

std::istream& operator>>(std::istream& is, big_int& val)
{
   std::string s;
   Vector a;
   while (!is.eof() && isspace(is.peek()))
      is.get();
   if (is.peek() == '+')
      is.get();
   else if (is.peek() == '-')
      s.push_back(is.get());
   if (is.eof()) 
   {
      return is;
   }
   if (!isdigit(is.peek())) 
   {
      is.seekg(0, std::ios::end);
      is.setstate(std::ios::failbit);
      return is;
   }
   while (!is.eof() && isdigit(is.peek()))
      s.push_back(is.get());
   val = big_int(s);
   return is;
}